package syf.rank;

import java.util.Arrays;

public class MergeRank {
    public static void main(String[] args) {
//        int[] arr={9,5,7,6,2,4,3,1,0,8,-5,50,-12};
        int max=80000000;
        int[] arr=new int[max];
        //8万个随机的数组排序
        for (int i=0;i<max;i++){
            arr[i]=(int)(Math.random()*100);
        }
        int[]tmp=new int[arr.length];
//        System.out.println(Arrays.toString(arr));
        long now=System.currentTimeMillis();
        merAnd(arr,0,arr.length-1,tmp);
        long end=System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println(end-now);//1627ms左右

    }
    public static void merAnd(int[] arr,int left,int right,int[] tmp){
        int mid;
        if (left<right){
            mid=(left+right)/2;
            //左递归分解
            merAnd(arr,left,mid,tmp);
            //右递归分解
            merAnd(arr,mid+1,right,tmp);
            //融合
            merge(arr,left,mid,right,tmp);
        }
    }
    /**
     * 归并排序
     * @param arr 需要排序的数组
     * @param left 传递的需要融合的左边索引
     * @param mid 传递的中间索引
     * @param right 传递的需要融合的右边索引
     * @param tmp 临时存放数组
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] tmp){
        //左边数组索引
        int l=left;
        //右边数组索引
        int r=mid+1;
        //临时数组索引
        int t=0;
        //当左边数组索引小于等于中间值并且右边数组小于整个数组最右边时，进行对tmp数组赋值
        while (l<=mid&&r<=right){
            //左边小于等于右边，把左边放在tmp中
            if (arr[l]<=arr[r]){
                tmp[t++]=arr[l++];
            }else {
                tmp[t++]=arr[r++];
            }
        }
        //退出时其中有一个不为空，要将剩余的值赋给tmp
        while (l<=mid){
            tmp[t++]=arr[l++];
        }
        while (r<=right){
            tmp[t++]=arr[r++];
        }
        //将tmp数组中的值拷贝到arr数组中
        t=0;
        int index=left;
        while (index<=right){
            arr[index++]=tmp[t++];
        }
    }
//    /**
//     * 合并
//     * @param arr 要分解的数组
//     * @param tmp 临时存放数组
//     */
//    public static void merAnd(int[] arr,int left,int right,int[] tmp){
//        int mid;
//        if (left<right){
//            mid=(left+right)/2;
//            //左递归分解
//            merAnd(arr,left,mid,tmp);
//            //右递归分解
//            merAnd(arr,mid+1,right,tmp);
//            //合并
//            merge(arr,left,mid,right,tmp);
//        }
//    }
//    /**
//     * 归并排序
//     * @param arr 待排序的数组
//     * @param left 左边有序序列的初始索引
//     * @param mid 中间索引
//     * @param right 右边索引
//     * @param tmp 做中转的数组
//     */
//    public static void merge(int[] arr,int left,int mid,int right,int[] tmp){
//        //左边数组的索引
//        int i=left;
//        //右边数组的索引
//        int j=mid+1;
//        //tmp数组的索引
//        int t=0;
//        //当左边数组索引大于中间索引，右边数组索引小于整个数组最右边时，继续进行数组融合否则退出融合
//        while (i<=mid&&j<=right){
//            //左边的数组小于等于右边的数组时,将左边的放入临时数组中去
//            if (arr[i]<=arr[j]){
//                tmp[t++]=arr[i++];
//            }
//            //反之时，将右边的放入临时数组
//            else {
//                tmp[t++]=arr[j++];
//            }
//        }
//        //当以上分完后，再分配左右两个数组中有剩余的数组
//        //左边没分完
//        while (i<=mid){
//            tmp[t++]=arr[i++];
//        }
//        //右边没分完
//        while (j<=right){
//            tmp[t++]=arr[j++];
//        }
//        //将tmp数组拷贝到arr数组中去,并不是每次都是全部拷被,拷贝最开始是从上一次最左边拷贝的
//        t=0;
//        int tmpIndex=left;
//        while (tmpIndex<=right){
//            arr[tmpIndex++]=tmp[t++];
//        }
//    }
}
